Paper 2020/1160
Characterizing Deterministic-Prover Zero Knowledge
Nir Bitansky and Arka Rai Choudhuri
Abstract
Randomness is typically thought to be essential for zero knowledge protocols. Following this intuition, Goldreich and Oren (Journal of Cryptology 94) proved that auxiliary-input zero knowledge cannot be achieved with a deterministic prover. On the other hand, positive results are only known in the honest-verifier setting, or when the prover is given at least a restricted source of entropy.
We prove that removing (or just bounding) the verifier's auxiliary input, deterministic-prover zero knowledge becomes feasible:
- Assuming non-interactive witness-indistinguishable proofs and subexponential indistinguishability obfuscation and one-way functions, we construct deterministic-prover zero-knowledge arguments for
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2020
- Keywords
- zero knowledge
- Contact author(s)
-
nirbitan @ tau ac il
achoud @ cs jhu edu - History
- 2020-09-25: received
- Short URL
- https://ia.cr/2020/1160
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1160, author = {Nir Bitansky and Arka Rai Choudhuri}, title = {Characterizing Deterministic-Prover Zero Knowledge}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1160}, year = {2020}, url = {https://eprint.iacr.org/2020/1160} }